| 翻訳と辞書 |
| SO (complexity) ： ウィキペディア英語版 |
SO (complexity)
Second-order logic is an extension of first-order with second orders quantifiers, hence the reader should first read FO (complexity) to be able to understand this article. In descriptive complexity we can see that the languages recognised by SO formulae are exactly equal to the languages decided by Turing machines in the polynomial hierarchy. Extensions of SO with some operators also give us the same expressivity given by some well known complexity class,〔
*N. Immerman ''Descriptive complexity'' (1999 Springer), All information in this article can be checked in this book.〕 so it is a way to do proofs about the complexity of some problems without having to go to the algorithmic level.
== Definition and examples ==
We define second-order variable, a SO variable has got an arity and represent any proposition of arity , i.e. a subset of the -tuples of the universe. They are usually written in upper-case. Second order logic is the set of FO formulae where we add quantification over second-order variables, hence we will use the terms defined in the FO article without defining them again.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「SO (complexity)」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|